package com.qying.dataStructure.tree;


/**
 * 红黑数
 * 特殊的二叉查找树,任何一个节点的键值，大于左节点键值，小于右节点键值
 * 每个节点的键值都有颜色 非红即黑
 * 根节点是黑色的
 * 每个叶子节点是黑色的
 * 如果一个节点是红色的，则他子节点为黑色
 * 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
 * 第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
 * 第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
 *
 */
public class RBTree<T extends Comparable<T>> {

   private static final boolean RED = true;

   private static final boolean Black = false;

   private TreeNode<T> root;

    public static void main(String[] args) {
        int[] ints = {15, 1, 3, 6, 8, 20,22,43,67};
        RBTree<Integer> integerRBTree = new RBTree<>();
        for (int anInt : ints) {
            integerRBTree.insertNode(anInt);
        }
        System.out.println(integerRBTree.root.data);
    }


   public void insertNode(T data) {
       TreeNode<T> curr;
       TreeNode<T> parent = toTargetParent(data);
       if (parent == null) {
           curr = root = new TreeNode<T>(data);
       } else {
           if (data.compareTo(parent.data) < 0) {
               curr = parent.left = new TreeNode<>(data);
               curr.parent = parent;
           }else {
               curr = parent.right = new TreeNode<>(data);
               curr.parent = parent;
           }
       }
       fixupTree(curr);
   }

   private void fixupTree(TreeNode node) {
       TreeNode parent = null, grandParent = null;
       boolean parentColor = false, uncleColor = false;

       if (node != root) {
           parent = node.parent;
           grandParent = parent.parent;
           parentColor = parent.color;
           uncleColor = getUncleColor(node);
       }

       if (parent == null && node.color == RED) {
           node.color = Black;
       } else if (parentColor == RED && uncleColor == RED) {
           changecolor(grandParent);
           fixupTree(grandParent);
       }else if (parentColor == RED && uncleColor == Black){
           dispatchRotation(grandParent, parent, node);
       }
   }

   private void dispatchRotation(TreeNode grandParent, TreeNode parent, TreeNode child) {
       if (grandParent.left == parent) {
           if (parent.left == child) {
               rightRotation(grandParent);
           }else {
               leftRotation(parent);
               rightRotation(grandParent);
           }
       } else {
           if (parent.left == child) {
               rightRotation(parent);
               leftRotation(grandParent);
           }else {
               leftRotation(grandParent);
           }
       }
   }

   private void changecolor(TreeNode grandParent) {
       grandParent.color = RED;
       if (grandParent.left != null) {
           grandParent.left.color = Black;
       }

       if (grandParent.right != null) {
           grandParent.right.color = Black;
       }
   }

   private boolean getUncleColor(TreeNode node) {
       TreeNode parent = node.parent;
       return getBrotherColor(parent.parent == null ? node : parent);
   }

   private boolean getBrotherColor(TreeNode child) {
       TreeNode parent = child.parent;

       if (parent.left == child && parent.right != null) {
           return parent.right.color;
       }else if (parent.right == child && parent.left != null) {
           return parent.left.color;
       } else  {
           return Black;
       }

   }


   private void leftRotation(TreeNode curr) {
       TreeNode tparent = curr.right;
       TreeNode parent = curr.parent;

       tparent.color = Black;

       curr.right = tparent.left;

       if (tparent.left != null) {
           tparent.left.parent = curr;
       }

       curr.color =RED;
       curr.parent = tparent;
       tparent.left = curr;
       setChild(curr, tparent);
   }

   private void rightRotation(TreeNode curr){
       TreeNode tParent = curr.left;
       TreeNode parent = curr.parent;

       tParent.color = Black;
       curr.left = tParent.right;

       if (tParent.right != null) {
           tParent.right.parent = curr;
       }
       curr.color = RED;
       curr.parent = tParent;
       tParent.right = tParent;
       setChild(curr,tParent);
   }

   private void setChild(TreeNode roNode, TreeNode newParent) {
       TreeNode roparent = newParent.parent;
       if (roparent == null) {
           root = newParent;
       }else if (roparent.left == roNode) {
           roparent.left = newParent;
       }else {
           roparent.right = newParent;
       }
   }

   private TreeNode<T> toTargetParent(T data) {
       TreeNode<T>  curr = root;
       TreeNode<T>  parent = root;
       while (curr != null) {
           parent = curr;
           if (data.compareTo(curr.data) < 0) {
               curr =curr.left;
           }else {
               curr =curr.right;
           }
       }
       return parent;
   }


   static class TreeNode<T extends Comparable<T>> {
       T data;
       boolean color;
       boolean isDeleted;

       TreeNode<T> left;
       TreeNode<T> right;
       TreeNode<T> parent;

       public TreeNode(T data, boolean color) {
           this.data = data;
           this.color = color;
       }

       public TreeNode(T data) {
           this.data = data;
           this.color = RED;
       }
   }

}
